package com.cqs.leetcode.dp;

import com.cqs.leetcode.ds.ArraysUtils;

import java.util.*;

/**
 * lixw
 * 2021/11/5
 **/
public class LongestArithmeticSubsequence1218 {

    public int longestSubsequence(int[] arr, int difference) {
        int[] dp = new int[arr.length];
        int max = 1;
        Map<Integer, Integer> map = new HashMap<>(4);
        for (int i = 0; i < arr.length; i++) {
            dp[i] = 1;
            Integer idx = map.get(arr[i] - difference);
            if (idx != null) {
                dp[i] = Math.max(dp[i], dp[idx] + 1);
                if (dp[i] > max) {
                    max = dp[i];
                }
            }
            //这里要放在Integer idx = map.get(arr[i] - difference);后面 arr = [1,1,1,1,1], difference = 0
            map.put(arr[i], i);

        }
        return max;
    }


    public static void main(String[] args) {
        LongestArithmeticSubsequence1218 l = new LongestArithmeticSubsequence1218();
        List<Case> list = new ArrayList<>();

        list.add(new Case(new int[]{4, 12, 10, 0, -2, 7, -8, 9, -9, -12, -12, 8, 8}, 0));
        list.add(new Case(new int[]{1, 5, 7, 8, 5, 3, 4, 2, 1}, -2));
        list.add(new Case(new int[]{1, 1, 1}, 1));
        list.add(new Case(new int[]{1, 2, 3, 4, 5}, 1));
        list.add(new Case(new int[]{1, 2, 1}, 1));
        list.add(new Case(new int[]{1, 1, 1,1,1,1}, 0));

        for (Case c : list) {
            System.out.println(c + "====>" + l.longestSubsequence(c.arr, c.difference));
        }


    }

    private static class Case {
        private int[] arr = new int[0];
        private int difference = 0;

        public Case(int[] arr, int difference) {
            this.arr = arr;
            this.difference = difference;
        }

        @Override
        public String toString() {
            return "Case{" +
                    "arr=" + ArraysUtils.formatInts(arr) +
                    ", difference=" + difference +
                    '}';
        }
    }
}
